package Leetcode_Second_Brush;

import java.util.HashMap;
import java.util.Map;

public class Solution003 {
    public int lengthOfLongestSubstring1(String s) {
        if (s.length() <= 1)
            return s.length();
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c));
            }
            map.put(c, i);
            maxLength = Math.max(maxLength, i - left);
        }
        return maxLength;
    }

    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0)
            return 0;
        Map<Character, Integer> hashmap = new HashMap<Character, Integer>();
        int maxLength = 0; // 存储最长的子串长度
        int left = -1; // 当前子串的左边界，初始时为-1，因为右边界从0开始遍历
        for (int right = 0; right < s.length(); right++) {
            // 有边界的字符出现在 map 中，可能在滑动串口中也可能不在
            if (hashmap.containsKey(s.charAt(right)))
                // 以 abba 为例，不能保证 hashmap.get(s.charAt(i)) 一定在 left 的右边
                left = Math.max(left, hashmap.get(s.charAt(right)));
            // 将新字符插入队列
            hashmap.put(s.charAt(right), right);
            // 计算当前子串的长度并与max比较
            maxLength = Math.max(maxLength, right - left); // 注意这里不能写max(max,i - hashmap.get(s.charAt(i)))
        }
        return maxLength;
    }
}
